package leetcode.editor.cn;

//[188]买卖股票的最佳时机 IV
public class BestTimeToBuyAndSellStockIv188 {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockIv188().new Solution();

        System.out.println("BestTimeToBuyAndSellStockIv188:main:" + solution.maxProfit(2, new int[]{2, 4, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //k 只算 买的时候。。。
        //执行耗时:9 ms,击败了13.77% 的Java用户 //	内存消耗:46.9 MB,击败了18.89% 的Java用户
        public int maxProfit(int k, int[] prices) {
            if (k < 1 || prices == null || prices.length < 1) return 0;
            int len = prices.length;
            int res = 0;

            int[][][] dp = new int[len][k + 1][2];
            for (int i = 0; i < len; i++) {
                for (int j = 0; j <= k; j++) {
                    //init
                    if (j == 0) {
                        dp[i][0][0] = 0;
                        dp[i][0][1] = Integer.MIN_VALUE;// TODO 重点
                        continue;
                    }
                    if (i == 0) {
                        dp[0][j][0] = 0;// TODO 重点
//                        dp[0][j][0] = Integer.MIN_VALUE; // TODO 重点
                        dp[0][j][1] = -prices[i];// TODO 重点
//                        dp[0][j][1] = Integer.MIN_VALUE;
                        continue;
                    }

                    dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                    res = Math.max(Math.max(dp[i][j][0], dp[i][j][1]), res);
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}